package com.example.binarytree;

import com.example.structure.Node;
import com.example.structure.TreeNode;

import java.util.*;

/**
 * @author wxz
 * 二叉树遍历算法-----二叉树类的题一定要想着倒换顺序，很可能就出现非常容易的解题方法
 */
public class Traversal {

    /**
     * 二叉树之字层序遍历算法
     * <p>
     * add(addLast)+poll(pollFirst) =队列
     * push(addFirst)+poll(pollFirst) =栈
     */
    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null) return lists;
        //用linklist，整个作为队列遍历树，前半部分看成栈1，后半部分看成栈2.做到每一层的节点依次放到不同栈中。
        Deque<TreeNode> dequeue = new LinkedList<>();
        dequeue.addFirst(root); //开始从前面进前面出
        int count = 0;  //计数。从偶数开始
        while (!dequeue.isEmpty()) {    //队列用来遍历树
            int curSize = dequeue.size();   //获取当前层的元素个数
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < curSize; i++) { //遍历当前层所有节点
                if (count % 2 == 0) { //偶数，从前面栈中取元素。并分别将左子节点和右子节点放到后面栈中
                    TreeNode first = dequeue.pollFirst();
                    list.add(first.val);
                    //todo 先后后，后先先
                    if (first.left != null) dequeue.addLast(first.left);
                    if (first.right != null) dequeue.addLast(first.right);
                } else {    //奇数，从后面栈中取元素。并分别将右子节点和左子节点放到前面栈中
                    TreeNode right = dequeue.pollLast();
                    list.add(right.val);
                    if (right.right != null) dequeue.addFirst(right.right);
                    if (right.left != null) dequeue.addFirst(right.left);
                }
            }
            count++;    //计数+1
            lists.add(list);    //list添加到总list中
        }
        return lists;
    }

    /**
     * 二叉树前序遍历算法---用栈做中转，根左右的方式入栈
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                res.add(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }
        return res;
    }

    /**
     * 二叉树中序遍历算法
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> stack = new LinkedList();
        while (root != null || !stack.isEmpty()) {
            //if else
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }

    /**
     * 中序递归
     */
    private void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        System.out.println(node);
        inorder(node.right);
    }

    /**
     * 二叉树后序遍历算法  反转链表法，类似前序，把前序改为根右左，然后反转链表即可左右根！！
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        while (root != null || stack.size() > 0) {
            while (root != null) {
                res.add(root.val);
                stack.push(root);
                root = root.right;
            }
            root = stack.pop();
            root = root.left;
        }
        Collections.reverse(res);
        return res;
    }

    /**
     * 二叉树后序遍历算法  反转链表法
     */
    public List<Integer> postorderTraversal1(TreeNode root) {
        List<Integer> res = new LinkedList();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> stack = new LinkedList();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }

    /**
     * 二叉树层序遍历算法
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }
        Deque<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            ret.add(level);
        }
        return ret;
    }

    /**
     * N叉树层序遍历
     */
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Deque<Node> queue = new LinkedList<>();
        queue.add(root);
        while (queue.size() > 0) {
            List<Integer> path = new ArrayList<>();
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                Node node = queue.poll();
                path.add(node.val);
                for (Node nn : node.children) {
                    queue.add(nn);
                }
            }
            res.add(path);
        }
        return res;
    }

    /**
     * 589. N 叉树的前序遍历
     * 给定一个 N 叉树，返回其节点值的 前序遍历 。
     * <p>
     * N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
     */
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Deque<Node> queue = new LinkedList<Node>() {{
            add(root);
        }};
        while (queue.size() > 0) {
            Node node = queue.pollLast();
            res.add(node.val);
            Collections.reverse(node.children);
            for (Node nn : node.children) {
                queue.add(nn);
            }
        }
        return res;
    }

    /**
     * 590. N 叉树的后序遍历
     * 给定一个 N 叉树，返回其节点值的 后序遍历 。
     * <p>
     * N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
     */
    public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Deque<Node> queue = new LinkedList<Node>() {{
            add(root);
        }};
        while (queue.size() > 0) {
            Node node = queue.pollLast();
            res.add(node.val);
            for (Node nn : node.children) {
                queue.add(nn);
            }
        }
        Collections.reverse(res);
        return res;
    }

    /**
     * 559. N 叉树的最大深度
     */
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }
        int maxChildDepth = 0;
        List<Node> children = root.children;
        for (Node child : children) {
            int childDepth = maxDepth(child);
            maxChildDepth = Math.max(maxChildDepth, childDepth);
        }
        return maxChildDepth + 1;
    }

    /**
     * 111. 二叉树的最小深度--递归
     */
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left != null && root.right == null) {
            return 1 + minDepth(root.left);
        }
        if (root.right != null && root.left == null) {
            return 1 + minDepth(root.right);
        }
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }

    /**
     * 111. 二叉树的最小深度--迭代
     */
    public int minDepthBystack(TreeNode root) {
        if (root == null) return 0;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int depth = 0;
        while (queue.size() > 0) {
            int n = queue.size();
            depth++;
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null) return depth;
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        return depth;
    }

    /**
     * 199. 二叉树的右视图
     * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
     * 示例 1:
     * <p>
     * 输入: [1,2,3,null,5,null,4]
     * 输出: [1,3,4]
     * <p>
     * 利用层序遍历每一层的最后元素即为右视图
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        if (root == null) return res;
        queue.add(root);
        while (queue.size() > 0) {
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                if (i == n - 1) res.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return res;
    }

    /**
     * 116. 填充每个节点的下一个右侧节点指针
     * 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
     * <p>
     * struct Node {
     * int val;
     * Node *left;
     * Node *right;
     * Node *next;
     * }
     * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
     * <p>
     * 初始状态下，所有 next 指针都被设置为 NULL。
     */
    public Node connect(Node root) {
        if (root == null) return null;
        Node dummy = root;
        Deque<Node> queue = new LinkedList<>();
        queue.add(root);
        while (queue.size() > 0) {
            int n = queue.size();
            Node pre = null;
            for (int i = 0; i < n; i++) {
                Node node = queue.poll();
                if (pre != null) pre.next = node;
                pre = node;
                if (i == n - 1) node.next = null;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return dummy;
    }
}


/**
 * 98. 验证二叉搜索树
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * <p>
 * 有效 二叉搜索树定义如下：
 * <p>
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 * <p>
 * 示例 1：
 * <p>
 * 输入：root = [2,1,3]
 * 输出：true
 */
class IsValidBST {
    long pre = Long.MIN_VALUE; // 记录上一个节点的值，初始值为Long的最小值

    public static void main(String[] args) {
        Deque<Integer> integerDeque = new LinkedList<>();
        integerDeque.addFirst(2);
        integerDeque.addFirst(3);
        integerDeque.addFirst(4);
        //integerDeque.add(5);
        //integerDeque.add(6);
        //integerDeque.add(7);
        // integerDeque.pollFirst();
        // integerDeque.pollLast();
        integerDeque.poll();
        integerDeque.pop();

    }

    public boolean isValidBST(TreeNode root) {
        return inorder(root);
    }

    // 中序遍历
    private boolean inorder(TreeNode node) {
        if (node == null) return true;
        boolean left = inorder(node.left);
        if (node.val <= pre || !left) return false;
        pre = node.val;
        boolean right = inorder(node.right);
        return left && right;
    }

    /**
     * 递归法
     */
    public boolean isValidBST2(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }
}

/**
 * 530. 二叉搜索树的最小绝对差
 * 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
 * <p>
 * 差值是一个正数，其数值等于两值之差的绝对值。
 * <p>
 * 思路：有二叉搜索树类似的题目，首先要想到中序遍历！！变为有序数组
 */
class GetMinimumDifference {
    int min = Integer.MAX_VALUE;
    int pre = -1;

    public int getMinimumDifference(TreeNode root) {
        inorder(root);
        return min;
    }

    public void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        if (pre != -1) {
            min = Math.min(Math.abs(node.val - pre), min);
        }
        pre = node.val;
        inorder(node.right);
    }
}

